// 1.辗转相除法
// 两个正整数a 和b（a>b），他们的最大公约数等于a除以b的余数c和b之间的最大公约数

//有了这条定理，求最大公约数就变得简单了。我们可以使用递归的方法把问题逐步简化。
//首先，计算出a除以b的余数c，把问题转化成求b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求c和d的最大公约数；再计算出c除以d的余数e，把问题转化成求d和e的最大公约数……
//以此类推，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1为止。



function getGreatestCommonDivisor(a,b){
    let big = a>b?a:b;
    let small = a<b?a:b;
    if(big%small == 0){
        return small;
    }
    return getGreatestCommonDivisor(big%small,small)
}
console.log(getGreatestCommonDivisor(25,15));


//2.更相减损法
//  两个正整数a 和b（a>b），他们的最大公约数等于a-b的差值c和较小数b之间的最大公约数
function getGreatestCommonDivisor2(a,b){
    if(a==b){
        return a;
    }
    let big = a>b?a:b;
    let small = a<b?a:b;
    return getGreatestCommonDivisor2(big-small,small);
}
console.log(getGreatestCommonDivisor2(25,15));
console.log(getGreatestCommonDivisor2(27,14));

//3. 把辗转相除法和更相减损法的优势结合起来，在更相减损法的基础上使用移位运算
// getGreatestCommonDivisor  简写为  gcb
// 对于给出的正整数 a 和 b，不难得到如下的结论，
// 当a和b均为偶数时，gcd(a,b) = 2 × gcd(a/2,b/2) = 2 ×gcd(a>>1,b>>1)
// 当a为偶数,b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a>>1,b)
// 当a为奇数,b为偶数时，gcd(a,b) = gcd(a,b/2) = gcd(a,b>>1)
// 当a,b为奇数时，先利用更相减损法运算一次  gcd(a,b) = gcd(a-b,b),此时必然是偶数，然后继续移位运算

// 判断整数奇偶性的方式 让整数和1进行与运算，如果 (a&1) == 0,则说明整数a是偶数; 如果 (a&1) != 0,则说明整数a是奇数; 

//在计算机编程中，特别是在C语言这样的低级语言中，“a & 1”表达式代表按位与操作符（bitwise AND operation）应用于变量 a 和数字 1。

//按位与操作是将两个二进制数的每一位分别进行逻辑与运算（AND），只有当两个对应位都是1时，结果位才为1，否则为0。由于“1”的二进制形式是 00000001（假设是8位机器），所以对任何整数 a 与 1 进行按位与操作的结果就是 a 的最低位（最右边的那一位）的值。

//具体应用中，常常用 a & 1 来检查一个整数 a 是否为奇数。因为对于任何整数，如果它是奇数，那么它的二进制表示的最低位必定是1；如果是偶数，则最低位一定是0。因此，a & 1 结果为1则表明 a 是奇数，结果为0则表明 a 是偶数。



function gcd(a,b){
    if(a==b){
        return a;
    }
    if((a&1)==0 && (b&1)==0){
        return gcd(a>>1,b>>1);
    }else if((a&1)==0 && (b&1)!=0){
        return gcd(a>>1,b);
    }else if((a&1)!=0 && (b&1)==0){
        return gcd(a,b>>1);
    }else{

        let big = a>b?a:b;
        let small = a<b?a:b;
        return gcd(big-small,small);
    }
}

console.log(gcd(25,15));
console.log(gcd(27,14));